package com.xj.datastructure.sort;

/**
 * author: xiajun
 * Date: 2014-07-20
 * Time: 19-28-00
 * 给定两个有序数组，求第K个数是多少
 * 1,假设 k=i+j
 * 2,转成数组下标 (k-1)=(i-1)+(j-1)//不是完整数学公式,而是结合数组下标的实际情况
 * > 例: 1,2,6||5,8,9  当k=3
 * > v[k]=3=b[0] => a[0],a[1],b[0],a[2],b[1],b[2]
 * > v_k=2,a_i=1,b_j=0 =>下标
 * > (3-1)=(2-1)+(1-1) =>3=2+1
 * 3,通过二分查找法迭代出最小符合条件2的两个下标值
 * > index=left+(right-left)/2 假设数组A的中间点为i
 * > j=k-i-1  //由条件2得出
 * 4,这2个值中大的那个就为K的值
 */
public class TopKII {
    public static void main(String[] args) {
        int[] b = {1, 3, 7, 10,34,56};
        int[] a = {2, 5, 6, 8, 9,35,67,89};
        TopKII top = new TopKII();
        int k = top.getK(a, b,9);
        System.out.println(k);
    }

    public int getK(int[] a, int[] b, int k) {
        if (k < 1) {
            throw new IllegalArgumentException("参数k必须大于0。");
        }
        if (a == null || b == null || a.length < 1 || b.length < 1) {
            throw new IllegalArgumentException("参数数组a、b不能为空。");
        }
        if (k < 2) {
            return a[0] > b[0] ? a[0] : b[0];
        }
        if(a.length>b.length){
            int []tmp=a;
            a=b;
            b=tmp;
        }
        int left = 0, right = Math.min(a.length,k);//目标下标必定不会大于k或a的长度
        while (left < right) {
            int i = left + (right - left) / 2;
            int j = k - i - 1;
            if (j > 0 && (j >= b.length || a[i] < b[j])) {//如果计算出来的j超过b数组的下标，那边必定要去a的右方查找
                left = i + 1;
            } else {
                right = i;
            }
        }
        return a[left-1] > b[k - left - 1] ? a[left-1] : b[k - left - 1];
    }
}
